package 动态数组实现4_17;

/**
 * 基于int整形的动态数组，根据元素的个数来调整动态数组大小
 */
import java.util.Arrays;
import java.util.Scanner;
public class MyArray {

    //先创造 整形数组类型 然后让用户传入数据指定数组大小
    private int[] data;
    //表示当前有效元素的个数
    private int size;

    //如果用户忘记输出数组大小，设置一个初始的大小
    public MyArray(){
        this(10);
    }

    //有参构造函数
    public MyArray(int initCap){

        this.data = new int[initCap];
    }

    //设置添加数据的功能 add
    public void add(int val){

        data[size] = val;
        size++;

        //每次添加完一个数就考虑是否需要增容，这样才能保证
        //数组每次都剩余位置
        if(size == data.length){
            grow();
        }
    }

    /**
     * 使数组增容，每次扩大为原来的两倍
     * 使用 Arrays.copyOf
     */
    private void grow() {
        //表示数组已经满了
        this.data = Arrays.copyOf(data, data.length * 2);
        System.out.println("扩容成功！");
    }

    /**
     * 因为println打印 对象 时会自动调用toString方法
     * 打印的却是地址，我们想要打印数组内容就要被toString方法
     * 进行重写，重定义。
     * @return
     */
    //完成打印数组内容的功能 补充下toString的功能
    public String toString(){

        String ret = "[";
        for (int i = 0; i < size; i++) {

            ret += data[i];
            if(i !=  (size - 1)){
                ret += ", ";
            }
        }
        ret += "]";
        return ret;
    }

    //在动态数组 index 位置处 插入 某个元素
    public void add(int val, int index){

        if(index < 0 || index > size){
            System.out.println("插入位置错误，重新输入");
            return;
        }
        for (int i = size; i > index; i--) {

            data[i] = data[i - 1];
        }
        data[index] = val;
        size++;
        System.out.println("插入成功");
        //考虑插入后是否需要扩容
        if(size == data.length){
            grow();
        }
    }

    //查：
    //若是返回 -1 则是没有，不存在
    //1. 第一种，查询当前动态数组中第一个值为val的元素,然后返回索引
    public int getByValue(int val){

        for (int i = 0; i < size; i++) {

            if(data[i] == val)
                return i;
        }
        return -1;
    }
    //2. 第二种，查询当前动态数组中是否包含值为val的元素，若存在返回true，否则返回false
    public boolean contains(int val){

        int rep = getByValue(val);
        return rep != -1;
    }
    //3.第三种，查询当前动态数组中索引为index的元素值
    public int get(int index){
        //判断是否越界查询
        if(index < 0 || index >= size){
            System.out.println("查询位置无效，请重新输入");
            return -1;
        }

        return data[index];

    }

    //改
    //1. 修改index位置的元素为新值的newVal，返回修改前的值
    public int set(int newVal, int index){
        //判断index的合法性
        if(index < 0 || index >= size){
            System.out.println("输入修改的位置不合理，请重新输入");
            return -1;
        }
        int tmp = data[index];
        data[index] = newVal;
        return tmp;

    }

    //2. 修改第一个值为oldVal的元素，更新为新的值newVal，返回是否修改成功
    public boolean setValue(int oldVal, int newVal){

        int tmp = getByValue(oldVal);
        if(tmp == -1){
            return false;
        }else{

            data[tmp] = newVal;
            return true;
        }
    }

    //删除
    //1.删除 索引为 index 的对应元素 返回删除前的元素值
    public int remove(int index){
        //判断 index 的合理性
        if(index < 0 || index >= size){

            System.out.println("删除的位置不存在、不合理！");
            return -1;
        }
        //判断如果里面没东西可以删除了，就不做改变
        if(size <= 0)
            return -1;

            int tmp = data[index];
        for (int i = index; i < size - 1; i++) {


                data[i] = data[i + 1];
        }
        size--;
        return tmp;
    }

    //2. 删除数组的头元素
    public int removeFirst(){

        //判断如果里面没东西可以删除了，就不做改变
        if(size <= 0)
            return -1;

        int ret = data[0];
        remove(0);
        return ret;
    }
    //3 删除数组的尾元素
    public int removeLast(){

        //判断如果里面没东西可以删除了，就不做改变
        if(size <= 0)
            return -1;

        int ret = data[size - 1];
        remove(size - 1);
        return ret;
    }
    //4 删除第一个为 val 的元素 返回是否删除成功
    public boolean removeBylueOnce(int val){

        int tmp = getByValue(val);
        if(tmp != -1){
            remove(tmp);
            return true;
        }
        return false;
    }

    //5.删除动态数组中所有为 val的元素
    public void removeBylueOnceplus(int val){

        //这是第二种方法，比较优，时间复杂度O（N）
        int p1 = 0;//用于接收不是val的数
        int p2 = 0;//遇到是val的数直接跳过

        while(p2 < size){
            if(data[p2] != val){
                data[p1] = data[p2];
                p1++;
            }
            p2++;
        }

        size = p1;

        //这是第一种 比较普通的方法
//        for (int i = 0; i < size; i++) {
//
//            //这里一定要添加判断条件 i < size
//            //不然如果要删除在元素在末尾时，我们的remove只是
//            //把size--了，并没有物理上删除最后一个元素，这里 data[i] == val 恒成立，死循环
//            while(data[i] == val && i < size ){
//                remove(i);
//            }
//        }

    }

}